package top.humbleyuan.leet;

import org.junit.Test;
import top.humbleyuan.leet.datastructure.linkedlist.*;

import java.util.*;

/**
 * @Author YHH
 * @Date 2019/9/10 10:45
 * @Des
 */

/**
 * 1.注意添加头结点
 * 2.使用快慢指针等价双循环
 * 3.将链表闭合成环在适当地方断开
 */
public class LinkedList {

    /**
     * 删除倒数n个 19
     */
    @Test
    public void link19() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(1);
        int[] vals = {2,3};
        head = LinkNode.formLink(head,vals);
        int n = 3;


        LinkNode f = head;
        int i ;
        for(i = 0;f != null;i++) {
            f = f.next;
        }
        if( i == n) {
            head = head.next;
            LinkNode.headToString(head);
            return;
        }

        f = head;
        //把i-n连到i-n+2上
        for(int j = 1;j < i - n;j++) {
            f = f.next;
        }
        f.next = f.next.next;

        LinkNode.headToString(head);

    }

    /**
     * niuke剑指offer_14
     */
    @Test
    public void link19_2() {
        /**
         * 一次遍历，快慢指针
         */
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(1);
        int[] vals = {2};
        head = LinkNode.formLink(head,vals);
        int n = 2;

        LinkNode fast = head;
        LinkNode slow = head;

        int i;
        for(i = 0;fast.next != null;i++) {

            fast = fast.next;
            if(i >= n)
                slow = slow.next;
        }

        /**
         * slow的next就是倒数第k个节点
         */
        slow.next = slow.next.next;

        LinkNode.headToString(head);

    }

    /**
     * 交换相邻节点
     */
    @Test
    public void Link24() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(1);
        int[] vals = {2,3,4};
        head = LinkNode.formLink(head,vals);


        if(head == null) {
            System.out.println("");
            return;
        }

        if(head.next == null) {
            LinkNode.headToString(head);
            return;
        }


        LinkNode pre = new LinkNode(0);
        pre.next = head;

        LinkNode f1 = pre;

        LinkNode f = head;
        while(f != null && f.next != null) {
            LinkNode f2 = f.next.next;

            f1.next = f.next;
            f.next.next = f;
            f.next = f2;

            f1 = f;
            f = f.next;
        }

        LinkNode.headToString(pre.next);
    }

    /**
     * 旋转链表
     */
    @Test
    public void link61() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(1);
        int[] vals = {2,3,4,6,7,8};
        head = LinkNode.formLink(head,vals);
        int k = 7;

        LinkNode pre = new LinkNode(0);
        pre.next = head;

        LinkNode temp = head;
        int i;
        for(i = 1;temp.next != null;i++) {
            temp = temp.next;
        }
        LinkNode end = temp;

        temp = head;
        int n = k % i;
        if(n == 0) {
            LinkNode.headToString(head);
            return ;
        }
        //找到倒数第n+1个位置,正数i-n
        for(int j = 0;j < i - n - 1;j++) {
            temp = temp.next;
        }

        pre.next = temp.next;
        temp.next = null;

        end.next = head;
        LinkNode.headToString(pre.next);
    }

    /**
     * 删除重复元素
     */
    @Test
    public void link82() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(1);
        int[] vals = {2,3,3,4,4,5,6,7,7,8,9 };
        head = LinkNode.formLink(head,vals);

        boolean flag = false;

        LinkNode root = new LinkNode(0);
        root.next = head;

        int preVal = head.val ;
        LinkNode temp = head.next;
        LinkNode preLink = root;

        while (temp != null) {
            if(temp.val == preVal) {
                flag = true;
                if(temp.next == null) {
                    preLink.next = null;
                    break;
                }
            }
            else {
                if(flag) {
                    preLink.next = temp;
                    flag = false;
                }
                else {

                    preLink = preLink.next;
                }
                preVal = temp.val;
            }
            temp = temp.next;
        }

        LinkNode.headToString(root.next);
    }

    @Test
    public void link82_2() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(1);
        int[] vals = {2,3,3,4,4,5};
        head = LinkNode.formLink(head,vals);

        LinkNode root = new LinkNode(0);
        root.next = head;

        //快慢指针
        //前一个和后一个比
        LinkNode slow = root;
        LinkNode fast = head;

        while (fast != null) {
            if(fast.next == null) {
                if(slow.next != fast)
                    slow.next = null;
                break;
            }

            if(fast.val != fast.next.val) {

                //前面有多个重复指针
                if(slow.next != fast) {
                    slow.next = fast.next;
                }else {
                    slow = fast;
                }
            }

            fast = fast.next;
        }
        LinkNode.headToString(root.next);
    }

    /**
     * 分隔链表
     */
    @Test
    public void link86() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(1);
        int[] vals = {4,3,2,5,2};
        head = LinkNode.formLink(head,vals);

        int x = 3;

        LinkNode left = new LinkNode(0);
        LinkNode right = new LinkNode(0);


        LinkNode leftTemp = left;
        LinkNode rightTemp = right;


        while (head != null) {
            if(head.val < x) {
                leftTemp.next = head;
                leftTemp = leftTemp.next;
            } else if(head.val >= x) {
                rightTemp.next = head;
                rightTemp = rightTemp.next;
            }

            head = head.next;
        }
        rightTemp.next = null;
        leftTemp.next = right.next;


        LinkNode.headToString(left.next);

    }

    /**
     * 翻转链表2
     */
    @Test
    public void link92() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(1);
        int[] vals = {4,3,6,7,8};
        head = LinkNode.formLink(head,vals);

        LinkNode root = new LinkNode(0);
        root.next = head;

        int m = 1,n = 3;
        LinkNode temp = head;
        LinkNode back = null ;
        LinkNode preTemp = root;
        LinkNode pre = null;
        LinkNode preNext = null;

        int i = 1;
        while(i <= n) {
            if(i >= m) {
                if(i == m) {
                    pre = preTemp;
                    preTemp = temp;
                    back = temp.next;
                    preNext = preTemp;
                    temp = back;
                    i++;
                    continue;
                }
                back = temp.next;
                temp.next = preTemp;
                preTemp = temp;
                temp = back;
                i++;
                continue;
            }
            preTemp = temp;
            temp = temp.next;
            i++;
        }

        preNext.next = back;
        pre.next = preTemp;

        LinkNode.headToString(root.next);
    }

    /**
     * 复制带随机指针的节点
     */
    @Test
    public void link138() {

        /**
         * 数据准备
         */
//        Node head = new Node(1);
//        int[] vals = {};
//        head = Node.formLink(head,vals);
        Node head = new Node(1,null,null);
        head.random = head;

        Node newNode = new Node(head.val,null,null);
        Node oldTemp = head;

        Node root = new Node(0,newNode,null);

        //老Node，新的深拷贝的Node
        Map<Node,Node> cloneNodeMap = new HashMap<>();

        //newNode先要放进去
        cloneNodeMap.put(oldTemp,newNode);

        while (oldTemp != null) {
            newNode.next = this.getCloneNode(oldTemp.next,cloneNodeMap);
            newNode.random = this.getCloneNode(oldTemp.random,cloneNodeMap);

            oldTemp = oldTemp.next;
            newNode = newNode.next;
        }

        System.out.println(11);

    }

    public Node getCloneNode(Node o,Map<Node,Node> map) {
        if(o == null)
            return null;
        if( !map.containsKey(o)) {
            map.put(o,new Node(o.val,null,null));
        }

        return map.get(o);
    }


    /**
     * 是否有环
     */
    @Test
    public void link141() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(3);
        int[] vals = {2,0,-4};

        //末尾与第几个点结成环
        int ringIndex = 1;
        head = LinkNode.formLink(head,vals,ringIndex);


        LinkNode temp = head;
        Set<LinkNode> nodes = new HashSet<>();

        while(temp != null) {
            if(nodes.contains(temp)) {
                System.out.println("有环");
                return;
            }

            nodes.add(temp);
            temp = temp.next;
        }

        if(temp == null)
            System.out.println("无环");

    }

    /**
     * 快慢指针，效率较上面方法较高
     */
    @Test
    public void link141_2() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(3);
        int[] vals = {2,0,-4,8,7,9,6};

        //末尾与第几个点结成环
        int ringIndex = 5;
        head = LinkNode.formLink(head,vals,ringIndex);

        LinkNode fast = head,slow = head;

        int step = 0;
        while (fast != null) {
            if(fast.next == null) {
                System.out.println("无环");
                return;
            }
            step ++;
            fast = fast.next.next;
            if (slow == fast) {
                System.out.println("有环,index:" + step);
                return;
            }
            slow = slow.next;

        }

        System.out.println("无环");
    }


    /**
     * 返回环的第一个节点
     */
    @Test
    public void link142() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(3);
        int[] vals = {};

        //末尾与第几个点结成环
        int ringIndex = 0;
        head = LinkNode.formLink(head,vals,ringIndex);


        LinkNode temp = head;
        Map<LinkNode,Integer> linkNodeHashMap = new HashMap<>();

        int index = 0;
        while(temp != null) {
            if(linkNodeHashMap.containsKey(temp)) {
                System.out.println("有环,index:" + linkNodeHashMap.get(temp));
                return;
            }

            linkNodeHashMap.put(temp,index ++);
            temp = temp.next;
        }


        System.out.println("无环");

    }

    /**
     * 重排链表
     * 1.找到重点（两种情况）
     * 2.将后半段逆序
     * 3.逆序后的后半段依次插入前半段
     */
    @Test
    public void link143() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(1);
        int[] vals = {2,3,4};
        head = LinkNode.formLink(head,vals);

        LinkNode slow = head,fast = head;


        while (fast != null) {
            if(fast.next == null) {
                break;
            }

            slow = slow.next;
            fast = fast.next.next;
        }

        LinkNode inversePreTemp = slow;
        LinkNode inverseNextTemp = slow.next;

        inversePreTemp.next = null;
        //从slow(mid)往后逆置后半段链表
        while(inverseNextTemp != null) {

            LinkNode temp = inverseNextTemp.next;

            inverseNextTemp.next = inversePreTemp;
            inversePreTemp = inverseNextTemp;
            inverseNextTemp = temp;

        }

        LinkNode insertTemp = head;
        //inversePreNext为逆置后后半段的head
        while(inversePreTemp != null) {
            LinkNode temp1 = insertTemp.next;
            LinkNode temp2 = inversePreTemp.next;

            insertTemp.next = inversePreTemp;
            inversePreTemp.next = temp1;
            inversePreTemp = temp2;
            insertTemp = temp1;
        }

        slow.next = null;

        LinkNode.headToString(head);

    }

    /**
     * 对链表进行插入排序
     * 1.一个指针往后遍历
     * 2.每次遍历与前一个比对：
     *      2.1若大于等于前一个，继续往前
     *      2.2否则另取指针从头遍历，在刚好的位置插入，
     *
     *###注意要调整断开以及连接点的连接关系
     *###在设root节点的时候注意考虑首次root和head是不需要交换的
     */
    @Test
    public void link147() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(-2147483647);
        int[] vals = {-2147483648};
        head = LinkNode.formLink(head,vals);
        LinkNode root = new LinkNode(-1);
        root.next = head;

        LinkNode moveTemp = head;
        LinkNode preTemp = root;

        while (moveTemp != null) {

            if(moveTemp.val >= preTemp.val || moveTemp == head) {
                preTemp = moveTemp;
                moveTemp = moveTemp.next;
                continue;
            }

            LinkNode sortTemp = root.next;
            LinkNode preSortTemp = root;
            while (sortTemp != moveTemp) {
                if(sortTemp.val > moveTemp.val) {
                    LinkNode temp = moveTemp;
                    moveTemp = moveTemp.next;
                    preTemp.next = moveTemp;

                    preSortTemp.next = temp;
                    temp.next = sortTemp;
                    break;
                }
                preSortTemp = sortTemp;
                sortTemp = sortTemp.next;
            }

        }

        LinkNode.headToString(root.next);

    }

    /**
     * 链表排序
     * 归并排序
     */
    @Test
    public void link148() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(-3);
        int[] vals = {4,5,6,1,2,1,3,9,-7};
        head = LinkNode.formLink(head,vals);

        LinkNode.headToString(sort(head));
    }

    public LinkNode sort(LinkNode head) {
        if(head.next == null)
            return head;

        LinkNode mid = getMid(head);
        //分割
        LinkNode rightHead = mid.next;
        mid.next = null;

        return merge(sort(head),sort(rightHead));
    }

    public LinkNode getMid(LinkNode head) {

        if(head.next == null)
            return head;

        LinkNode slow = head,fast = head.next.next;
        while (fast != null) {
            if(fast.next == null)
                return slow.next;

            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public LinkNode merge(LinkNode left,LinkNode right) {
        if(left == null || right == null)
            return left == null ? right : left;

        LinkNode root = new LinkNode(-1);
        LinkNode temp = null;
        if(left.val <= right.val) {
            root.next = left;
            temp = left;
            left = left.next;
        }else {
            root.next = right;
            temp = right;
            right = right.next;
        }

        while (left != null && right != null) {
            if(left.val <= right.val) {
                temp.next = left;
                temp = left;
                left = left.next;
            } else {
                temp.next = right;
                temp = right;
                right = right.next;
            }
        }

        if(left != null) {
            temp.next = left;
        }else {
            temp.next = right;
        }

        return root.next;
    }


    /**
     * 相交链表
     * 双指针：从两个指针头开始，遍历完当前链表开始遍历第二个，会在相交点相遇
     */
    @Test
    public void link160() {
        /**
         * 生成相交链表
         */
        LinkNode firstHead = new LinkNode(2);
        int[] vals1 = {4, 3, 7, 8, 5, 6, 4};
        firstHead = LinkNode.formLink(firstHead, vals1);

        LinkNode secondHead = new LinkNode(7);
        int[] vals2 = {9, 8, 5, 6, 4};
        secondHead = LinkNode.formLink(secondHead, vals2);

        IntersectLinkedList intersectLinkedList =
                new IntersectLinkedList(firstHead, secondHead, 4, 2);

        firstHead = intersectLinkedList.getFirstHead();
        secondHead = intersectLinkedList.getSecondHead();

        int firstCycleIndex = 1,
            secondCycleIndex = 1;

        LinkNode firstTemp = firstHead;
        LinkNode secondTemp = secondHead;

        LinkNode firstEnd = null;
        LinkNode secondEnd = null;
        while (firstCycleIndex <= 2 && secondCycleIndex <= 2) {

            if((firstEnd != null && secondEnd != null) && firstEnd != secondEnd) {
                System.out.println("不相交");
                return;
            }
            if(firstTemp == secondTemp) {
                System.out.println("相交点:" + firstTemp.val);
                return;
            }

            if(firstTemp.next == null && firstCycleIndex <= 2) {
                firstEnd = firstTemp;
                firstTemp = secondHead;
                firstCycleIndex ++;
            }else {
                firstTemp = firstTemp.next;
            }

            if(secondTemp.next == null && secondCycleIndex <= 2) {
                secondEnd = secondTemp;
                secondTemp = firstHead;
                secondCycleIndex ++;
            }else {
                secondTemp = secondTemp.next;
            }

        }

    }

    /**
     * 移除链表元素
     */
    @Test
    public void link203() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(3);
        int[] vals = {};
        head = LinkNode.formLink(head,vals);
        int val = 3;

        LinkNode root = new LinkNode(0);
        root.next = head;

        LinkNode temp = root;

        while (temp != null && temp.next != null) {
            if(temp.next.val == val) {
                temp.next = temp.next.next;
                if(temp.next != null && temp.next.val == val)
                    continue;
            }
            temp = temp.next;
        }

        LinkNode.headToString(root.next);
    }

    /**
     * 反转链表
     */
    @Test
    public void link206() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(3);
        int[] vals = {6,7,8,3};
        head = LinkNode.formLink(head,vals);

        LinkNode temp = head;

        LinkNode preTemp = null;

        while (temp != null) {
            LinkNode backTemp = temp.next;
            temp.next = preTemp;
            preTemp = temp;
            temp = backTemp;
        }

        LinkNode.headToString(preTemp);
    }

    /**
     * 回文链表
     * 快慢指针
     * 1.慢指针找到中点，按顺序存储前半段值
     * 2.遍历后半段，比对
     */
    @Test
    public void link234() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(3);
        int[] vals = {4,4,6,4,4,3};
        head = LinkNode.formLink(head,vals);

        if(head == null || head.next == null) {
            System.out.println(false);
            return;
        }

        if(head.next.next == null) {
            String res = head.val == head.next.val ? "是回文链表" : "不是回文链表";
            System.out.println(res);
            return;
        }

        LinkNode slow = head;
        LinkNode fast = head.next.next;
        List<Integer> preHalfVals = new ArrayList<>();
        preHalfVals.add(slow.val);

        while (fast != null) {

            if(fast.next == null) {
                slow = slow.next;
                break;
            }

            slow = slow.next;
            preHalfVals.add(slow.val);
            fast = fast.next.next;
        }

        int index = preHalfVals.size();
        slow = slow.next;
        //slow往后半段走
        while (slow != null && !(index < 0)) {
            if(preHalfVals.get(index-1) != slow.val) {
                System.out.println("不是回文链表");
                return;
            }
            slow = slow.next;
            index--;
        }
        System.out.println("是回文链表");

    }


    /**
     * 奇偶链表
     * 双指针分别重连两半链表
     */
    @Test
    public void link328() {
        LinkNode head = new LinkNode(3);
        int[] vals = {};
        head = LinkNode.formLink(head,vals);

        LinkNode oddHead = head;
        LinkNode evenHead = head.next;

        LinkNode oddTemp = oddHead;
        LinkNode evenTemp = evenHead;
        while (oddTemp.next != null && (evenTemp != null && evenTemp.next != null)) {
            oddTemp.next = oddTemp.next.next;
            evenTemp.next = evenTemp.next.next;

            oddTemp = oddTemp.next;
            evenTemp = evenTemp.next;
        }
        oddTemp.next = evenHead;

        LinkNode.headToString(oddHead);
    }

    /**
     * 两数相加：
     *
     */
    @Test
    public void link445() {
        /**
         * 数据准备
         */
        LinkNode num1 = new LinkNode(6);
        int[] vals = {};
        num1 = LinkNode.formLink(num1,vals);

        LinkNode num2 = new LinkNode(8);
        int[] vals1 = {};
        num2 = LinkNode.formLink(num2,vals1);

        List<Integer> num1List = new ArrayList<>();
        List<Integer> num2List = new ArrayList<>();

        LinkNode numTemp = num1;
        while (numTemp != null) {
            num1List.add(numTemp.val);
            numTemp = numTemp.next;
        }

        numTemp = num2;
        while (numTemp != null) {
            num2List.add(numTemp.val);
            numTemp = numTemp.next;
        }

        int max1 = num1List.size() - 1;
        int max2 = num2List.size() - 1;
        List<Integer> sum = new ArrayList<>();
        int carry = 0;
        for( ; max1 >= 0 || max2 >= 0 ; max1--,max2--) {
            int bit1 = max1 < 0 ? 0 : num1List.get(max1);
            int bit2 = max2 < 0 ? 0 : num2List.get(max2);

            int bitSum = bit1 + bit2 + carry;
            sum.add(bitSum % 10);

            carry = bitSum > 9 ? 1 : 0;
        }
        if(carry == 1)
            sum.add(carry);

        LinkNode root = new LinkNode(0);
        LinkNode sumLink= new LinkNode();
        root.next = sumLink;
        for (int i = sum.size() - 1;i >= 0;i--) {
            sumLink.val = sum.get(i);

            if(i == 0) {
                sumLink.next = null;
                break;
            }
            sumLink.next = new LinkNode();
            sumLink = sumLink.next;
        }
        LinkNode.headToString(root.next);
    }

    /**
     * 分割链表
     */
    @Test
    public void link725() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(6);
        int[] vals = {};
        head = LinkNode.formLink(head,vals);
        int k = 1;

        LinkNode temp = head;
        int count = 0;

        //遍历一遍，计算长度
        while (temp != null) {
            temp = temp.next;
            count ++;
        }

        int mean = count / k;
        int remainder = count % k;

        //下方简化写法
        int partition = mean == 0 ? count : remainder == 0 ? k : remainder;
        //除数为0
//        if(mean == 0) {
//            //前count组1个，后k-count组为null
//            partition = count;
//        }
//        //余数为0
//        else if(remainder == 0) {
//            //k组，每组mean个
//            partition = k;
//        } else {
//            //remainder必定小于k,前remainder组mean+1个，后k-remainder组mean个
//            partition = remainder;
//
//        }

        LinkNode[] linkNodes = new LinkNode[k];
        temp = head;

        //前partition组
        for(int i = 0;i < k;i++) {
            int odd = i >= partition || remainder == 0 ? mean - 1 : mean;
            if(odd == -1) {
                linkNodes[i] = null;
                break;
            }

            LinkNode singleLink = temp;
            while (odd > 0){
                temp = temp.next;
                odd --;
            }
            LinkNode eTemp = temp.next;
            temp.next = null;
            linkNodes[i] = singleLink;
            temp = eTemp;
        }

        for(int i = 0;i < k;i++) {
            if(linkNodes[i] == null) {
                System.out.println("null");
                continue;
            }
            LinkNode.headToString(linkNodes[i]);
        }
    }

    /**
     * 扁平化多级双向链表
     * 遇到child先插入父级
     */
    @Test
    public void link430() {
        /**
         * 数据准备
         */
        BothWayNode head1 = new BothWayNode();
        head1.val = 2;

        int[] values1 = {3,6};
        head1.formListNode(values1);

        BothWayNode head2 = new BothWayNode();
        head2.val = 7;

        int[] values2 = {5,9,8};
        head2.formListNode(values2);

        BothWayNode head3 = new BothWayNode();
        head3.val = 9;

        int[] values3 = {7,0};
        head3.formListNode(values3);

        int point1 = 1,point2 = 1;
        int index = 0;

        BothWayNode temp = head1;
        while (index < point1) {
            temp = temp.next;
            index ++;
        }
        temp.child = head2;

        temp = head2;
        index = 0;
        while (index < point2) {
            temp = temp.next;
            index ++;
        }
        temp.child = head3;

        //扁平化
        temp = head1;
        while (temp != null) {
            if(temp.child == null) {
                temp = temp.next;
                continue;
            }

            //遇到有child时往父级收缩
            BothWayNode childTemp = temp.child;
            BothWayNode child = childTemp;
            temp.child = null;
            while (childTemp.next != null) {
                childTemp = childTemp.next;
            }
            //child插入父级
            childTemp.next = temp.next;
            if(temp.next != null)
                temp.next.prev = childTemp;

            temp.next = child;
            child.prev = temp;

            temp = temp.next;
        }
    }

    /**
     * 链表组件
     */
    @Test
    public void link817() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(6);
        int[] vals = {2,3,5,7};
        head = LinkNode.formLink(head,vals);

        int[] G = {2,5,7,9};

        Set<Integer> nums = new HashSet<>();
        int i = 0;
        while (i < G.length) {
            nums.add(G[i++]);
        }

        int count = 0;
        LinkNode temp = head;
        boolean inCom = false;
        while (temp != null) {
            if(nums.contains(temp.val) && !inCom) {
                inCom = true;
                count ++;
            }else if(!nums.contains(temp.val)){
                inCom = false;
            }
            temp = temp.next;
        }
        System.out.println(count);
    }

    /**
     * 设计链表
     */
    @Test
    public void link707() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(6);
        int[] vals = {2,3,5,7};
        head = LinkNode.formLink(head,vals);


        MyLinkedList myLinkedList = new MyLinkedList();
        //myLinkedList.first = head;
        //LinkNode.headToString(head);

        //查找
        //System.out.println(myLinkedList.get(3));

        myLinkedList.addAtHead(1);
        myLinkedList.addAtIndex(1,2);
        System.out.println(myLinkedList.get(1));
        LinkNode.headToString(myLinkedList.first);
    }


    /**
     * 取得中间节点
     * 快慢节点
     */
    @Test
    public void link876() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(6);
        int[] vals = {2,3,5,7,8};
        head = LinkNode.formLink(head,vals);
        LinkNode.headToString(head);

        if(head.next == null) {
            System.out.println(head.val);
            return;
        }


        LinkNode fast = head.next.next;
        LinkNode slow = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        System.out.println(slow.next.val);
    }

    /**
     * 链表中下一个更大节点
     */
    @Test
    public void link1019() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(2);
        int[] vals = {1,5};
        head = LinkNode.formLink(head,vals);

        Stack<MyEntry<Integer,Integer>> stack = new Stack<>();
        int[] largerArray = new int[10000];

        LinkNode temp = head;
        int length = 0;

        while (temp != null) {
            if(!stack.empty() && temp.val > stack.peek().getValue()) {
                largerArray[stack.peek().getKey()] = temp.val;
                stack.pop();
                continue;
            }
            stack.push(new MyEntry<>(length,temp.val));
            temp = temp.next;
            length ++;
        }

        Arrays.copyOfRange(largerArray,0,length);

    }

    //用数组代替entry
    @Test
    public void link1019_2() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(2);
        int[] vals = {7,4,3,5};
        head = LinkNode.formLink(head,vals);

        Stack<Integer> stack = new Stack<>();
        int[] largerArray = new int[10000];
        int[] arr1 = new int[10000];

        LinkNode temp = head;
        int length = 0;

        while (temp != null) {
            if(!stack.empty() && temp.val > stack.peek()) {
                largerArray[arr1[stack.size() - 1]] = temp.val;
                stack.pop();
                continue;
            }

            stack.push(temp.val);
            arr1[stack.size() - 1] = length;

            temp = temp.next;
            length ++;
        }

        Arrays.copyOfRange(largerArray,0,length);
    }

    //用动态变动数组代替栈，效率要高(别人)
    public void link1019_3() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(2);
        int[] vals = {1,5};
        head = LinkNode.formLink(head,vals);

        int[] stack = new int[10000];
        int[] res = new int[10000];
        int[] temp = new int[10000];
        int top = -1, i = 0;
        LinkNode node = head;

        while (node != null) {
            while (top != -1 && temp[stack[top]] < node.val)
                res[stack[top--]] = node.val;
            stack[++top] = i;
            temp[i++] = node.val;
            node = node.next;
        }
        Arrays.copyOf(res, i);
    }

    /**
     * 删去总和值为0的连续节点
     */
    @Test
    public void link1171() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(1);
        int[] vals = {2,3,-3,4};
        head = LinkNode.formLink(head,vals);

        LinkNode root = new LinkNode(-1);
        LinkNode preTemp = root;
        root.next = head;

        LinkNode firstCycle = head;
        while (firstCycle != null) {
            LinkNode secondCycle = firstCycle;
            int sum = firstCycle.val;

            while (sum != 0 && secondCycle.next != null) {
                secondCycle = secondCycle.next;
                sum += secondCycle.val;
            }

            if(sum == 0) {
                preTemp.next = secondCycle.next;
                firstCycle = secondCycle.next;
                continue;
            }
            preTemp = firstCycle;
            firstCycle = firstCycle.next;
        }

        LinkNode.headToString(root.next);

    }


    /**
     * 回文链表 O(1)空间
     */
    @Test
    public void leet_234() {
        LinkNode head = new LinkNode(1);
        int[] vals = {2,2,1};
        head = LinkNode.formLink(head,vals);
        System.out.println(charge(head));
    }

    public boolean charge(LinkNode head) {
        if(head == null || head.next == null) {
            return true;
        }
        if(head.next.next == null) {
            if(head.val == head.next.val) {
                return true;
            } else{
                return false;
            }
        }

        /**
         1. 快慢指针先找到中间；
         2. 再用慢指针逆置后半部链表
         3. 记录后半部指针头结点
         4. 比较两部分链表是否相同
         **/
        LinkNode slow = head, fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        if(fast != null && fast.next == null) {
            slow = slow.next;
        }

        LinkNode pre = slow;
        LinkNode back = pre == null ? null : pre.next;
        pre.next = null;
        // 逆置后半部
        while(back != null) {
            LinkNode lastTemp = back.next;
            back.next = pre;
            pre = back;
            back = lastTemp;
        }

        // 遍历pre
        while(pre != null) {
            if(pre.val != head.val) {
                return false;
            }
            pre = pre.next;
            head = head.next;
        }

        return true;
    }

}
